/*
 * @lc app=leetcode.cn id=662 lang=javascript
 *
 * [662] 二叉树最大宽度
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var widthOfBinaryTree = function (root) {
  // 使用完全二叉树的数组存储方式来查询每层的节点数量
  // 逐层扫描节点计算最大和最小索引
  if (root === null) return 0;
  // 队列列存储当前索引和节点
  const queue = [[1, root]];
  let result = 1;

  while (queue.length) {
    let size = queue.length;
    // 更新结果(每层结束的索引-开始的索引+1)
    result = Math.max(result, queue[queue.length - 1][0] - queue[0][0] + 1);
    // 位移值，防止结果溢出
    // 也可以用bigint类型
    let offset = queue[queue.length - 1][0];
    // 更新队列节点
    while (size-- > 0) {
      let [idx, node] = queue.shift();
      if (node.left) queue.push([idx * 2 - offset, node.left]);
      if (node.right) queue.push([idx * 2 + 1 - offset, node.right]);
    }
  }

  return result;
};
// @lc code=end
